//面试题 02.05. 链表求和

#include <stdlib.h>
struct ListNode {
    int val;
    struct ListNode *next;
};
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    if(NULL == l1) return l2;
    if(NULL == l2) return l1;

    struct ListNode* head = l1, * prev = NULL;
    int n = 0, carry = 0;
    while(l1 || l2)
    {  
        if(NULL == l1)
        {
            prev->next = l2;
            prev = prev->next;
            n = (prev->val + carry) / 10;
            prev->val = (prev->val + carry) % 10;
            carry = n;
            break;
        }
        else if(NULL == l2)
        {
            prev = prev->next;
            n = (prev->val + carry) / 10;
            prev->val = (prev->val + carry) % 10;
            carry = n;
            break;
        }
        else
        {
            n = (l1->val + l2->val + carry) / 10;
            l1->val = (l1->val + l2->val + carry) % 10;
            prev = l1;
            l1 = l1->next;
            l2 = l2->next;
            carry = n;
        }
    }
    while(prev->next)
    {
        prev = prev->next;
        n = (prev->val + carry) / 10;
        prev->val = (prev->val + carry) % 10;
        carry = n;
    }
    if(carry > 0)
    {
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = carry;
        node->next = NULL;
        prev->next = node;
    }
    return head;
}